# 路径(好题, 一个非常经典的dijkstra的最短路径)
import heapq
import math
from functools import reduce


def lcm(n1, n2):  # (15,225)  (3,45)*5  (1,15)*15   /  (15,25)  5*(3,5)
    # 求最小公倍数
    if n2 < n1:  # 确定n2大于n1
        n1, n2 = n2, n1

    if n2 % n1 == 0:  # 如果n1可以被n2整除, 就直接返回n2
        return n2

    mul = 1
    for i in range(2, n1):
        if n2 % i == 0 and n1 % i == 0:
            mul *= i
            n1, n2 = n1 // i, n2 // i
    return mul * n1 * n2


def lcm_multiple(*numbers: int) -> int:
    """计算多个数的最小公倍数（使用 reduce）"""
    if not numbers:
        return 0  # 处理空输入
    return reduce(lcm, numbers)


def shortest_path():
    """不使用小根堆的Dijkstra算法, 速度明显更慢"""

    def lcm(a, b):
        """求最大公倍数"""
        return a * b // math.gcd(a, b)

    dist = [float("inf")] * (2021 + 1)
    dist[1] = 0
    stack = [1]
    while stack:
        curr_node = stack.pop()

        for i in range(1, 22):
            next_node = curr_node + i
            if next_node < 2022:
                d = dist[curr_node] + lcm(curr_node, next_node)
                if d < dist[next_node]:
                    dist[next_node] = d
                    stack.append(next_node)

    return dist[2021]


def shortest_path_length(target):
    """使用小根堆的Dijkstra算法"""

    def lcm_opt(n1, n2):
        """一个优化的最小公倍数的求法
        lcm = a * b // gcd(a, b)
        """
        return n1 * n2 // (math.gcd(n1, n2))

    INF = float('inf')
    dist = [INF] * (target + 1)
    dist[0] = dist[1] = 0
    heap = [(0, 1)]  # 初始节点 (到节点1的路径长度, 当前节点)
    while heap:
        curr_d, curr = heapq.heappop(heap)  # 使用heapq来首先遍历较小的路径
        if curr_d > dist[curr]:
            continue  # 已存在更优路径，跳过

        for i in range(1, 22):
            nxt = i + curr
            if nxt > target:
                break
            d = dist[curr] + lcm_opt(curr, nxt)  # 节点1到目标节点的距离
            if d < dist[nxt]:
                dist[nxt] = d
                heapq.heappush(heap, (d, nxt))

    return dist[target]


if __name__ == '__main__':
    print(shortest_path_length(2021))  # 10266837
    print(shortest_path())  #
